package leetcode;

public class BestTimeToBuySellStock {
	public int maxProfitI(int[] prices) {
		if (prices == null || prices.length == 0 || prices.length == 1)
			return 0;

		int cbin = prices[0];
		int mprofit = 0;

		for (int i = 1; i < prices.length; ++i) {
			if (prices[i] < cbin)
				cbin = prices[i];
			else
				mprofit = Math.max(mprofit, prices[i] - cbin);
		}

		return mprofit;
	}

	public int maxProfitII(int[] prices) {
		if (prices == null || prices.length == 0 || prices.length == 1)
			return 0;

		int mprofit = 0;

		for (int i = 1; i < prices.length; ++i) {
			if (prices[i] >= prices[i - 1])
				mprofit += prices[i] - prices[i - 1];
		}

		return mprofit;
	}

	public int maxProfitIII(int[] prices) {
		if (prices == null || prices.length == 0 || prices.length == 1)
			return 0;

		int gprofit = 0;

		int[] prs = new int[prices.length];
		int[] fprs = new int[prices.length];
		int t = prices[0];
		prs[0] = 0;
		fprs[prices.length - 1] = 0;

		for (int i = 1; i < prices.length; ++i) {
			t = Math.min(t, prices[i]);
			prs[i] = Math.max(prs[i - 1], prices[i] - t);
		}

		t = prices[prices.length - 1];
		for (int i = prices.length - 1; i >= 0; --i) {
			t = Math.max(t, prices[i]);
			if (i < prices.length - 1) {
				fprs[i] = Math.max(fprs[i + 1], t - prices[i]);
			}
			gprofit = Math.max(gprofit, prs[i] + fprs[i]);
		}

		return gprofit;
	}
}
